package lianbiao;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author Stringzhua
 * @Date 2025/10/23 16:31
 * description:循环单链表
 */
public class CircularSinglyLinkedList {
    // 循环链表节点内部类
    static class Node {
        double data;  // 支持int和double（适配原代码中3.5、3.75等测试数据）
        Node next;

        // 节点构造方法
        public Node(double data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node head;  // 头节点
    private Node tail;  // 尾节点（优化操作效率）

    // 循环单链表构造方法
    public CircularSinglyLinkedList() {
        this.head = null;
        this.tail = null;
    }

    /**
     * 检查链表是否为空
     * @return 空返回true，非空返回false
     */
    public boolean isEmpty() {
        return head == null;
    }

    /**
     * 遍历链表并返回所有元素
     * @return 存储节点数据的List
     */
    public List<Double> traverse() {
        List<Double> result = new ArrayList<>();
        if (head == null) {
            return result;
        }

        // 采用do-while逻辑遍历（先添加头节点，再循环）
        Node current = head;
        result.add(current.data);
        current = current.next;

        // 指针回到头节点时停止
        while (current != head) {
            result.add(current.data);
            current = current.next;
        }
        return result;
    }

    /**
     * 在空链表中插入第一个节点
     * @param data 插入的节点数据
     * @return 插入成功返回true
     */
    private boolean insertEmpty(double data) {
        Node newNode = new Node(data);
        head = newNode;
        tail = newNode;
        newNode.next = newNode;  // 自循环，形成闭环
        return true;
    }

    /**
     * 在链表头部插入节点
     * @param data 插入的节点数据
     * @return 插入成功返回true
     */
    public boolean prepend(double data) {
        if (head == null) {
            return insertEmpty(data);
        }

        Node newNode = new Node(data);
        newNode.next = head;      // 新节点指向原头节点
        tail.next = newNode;      // 尾节点指向新节点（维持闭环）
        head = newNode;           // 更新头节点
        return true;
    }

    /**
     * 在链表尾部插入节点（使用尾指针优化）
     * @param data 插入的节点数据
     * @return 插入成功返回true
     */
    public boolean append(double data) {
        if (head == null) {
            return insertEmpty(data);
        }

        Node newNode = new Node(data);
        newNode.next = head;      // 新节点指向头节点（维持闭环）
        tail.next = newNode;      // 原尾节点指向新节点
        tail = newNode;           // 更新尾节点
        return true;
    }

    /**
     * 在链表尾部插入节点（不使用尾指针）
     * @param data 插入的节点数据
     * @return 插入成功返回true
     */
    public boolean appendWithoutTail(double data) {
        if (head == null) {
            return insertEmpty(data);
        }

        Node newNode = new Node(data);
        newNode.next = head;

        // 遍历找到尾节点（next指向头节点的节点）
        Node current = head;
        while (current.next != head) {
            current = current.next;
        }

        current.next = newNode;   // 原尾节点指向新节点
        tail = newNode;           // 更新尾节点（保持成员变量一致性）
        return true;
    }

    /**
     * 在指定数据的节点后插入新节点
     * @param targetData 目标节点的数据
     * @param data 新节点的数据
     * @return 插入成功返回true，失败返回false
     */
    public boolean insertAfter(double targetData, double data) {
        if (head == null) {
            return false;
        }

        Node current = head;
        while (true) {
            if (current.data == targetData) {
                // 找到目标节点，执行插入
                Node newNode = new Node(data);
                newNode.next = current.next;  // 新节点指向目标节点的下一个
                current.next = newNode;       // 目标节点指向新节点

                // 若目标节点是尾节点，同步更新尾指针
                if (current == tail) {
                    tail = newNode;
                }
                return true;
            }

            current = current.next;
            // 指针回到头节点，说明未找到目标
            if (current == head) {
                break;
            }
        }
        return false;
    }

    /**
     * 删除链表中唯一的节点
     * @return 删除成功返回true
     */
    private boolean deleteOnlyNode() {
        head = null;
        tail = null;
        return true;
    }

    /**
     * 删除头节点
     * @return 删除成功返回true，失败返回false
     */
    public boolean deleteHead() {
        if (head == null) {
            return false;
        }

        // 若只有一个节点，调用专用删除方法
        if (head == tail) {
            return deleteOnlyNode();
        }

        Node newHead = head.next;  // 新头节点是原头节点的下一个
        tail.next = newHead;       // 尾节点指向新头节点（维持闭环）
        head = newHead;            // 更新头节点
        return true;
    }

    /**
     * 删除尾节点
     * @return 删除成功返回true，失败返回false
     */
    public boolean deleteTail() {
        if (head == null) {
            return false;
        }

        // 若只有一个节点，调用专用删除方法
        if (head == tail) {
            return deleteOnlyNode();
        }

        // 找到尾节点的前一个节点
        Node current = head;
        while (current.next != tail) {
            current = current.next;
        }

        current.next = head;  // 前节点指向头节点（维持闭环）
        tail = current;       // 更新尾节点
        return true;
    }

    /**
     * 删除指定数据的节点
     * @param data 要删除的节点数据
     * @return 删除成功返回true，失败返回false
     */
    public boolean delete(double data) {
        if (head == null) {
            return false;
        }

        // 若只有一个节点且是目标节点
        if (head == tail && head.data == data) {
            return deleteOnlyNode();
        }

        // 若目标节点是头节点
        if (head.data == data) {
            return deleteHead();
        }

        // 查找目标节点的前驱节点
        Node prev = head;
        Node current = head.next;
        while (current != head) {
            if (current.data == data) {
                // 若目标节点是尾节点，同步更新尾指针
                if (current == tail) {
                    tail = prev;
                }
                prev.next = current.next;  // 前驱节点跳过目标节点
                return true;
            }
            prev = current;
            current = current.next;
        }

        return false;  // 未找到目标节点
    }

    /**
     * 查找指定数据的节点
     * @param data 要查找的数据
     * @return 存在返回true，不存在返回false
     */
    public boolean search(double data) {
        if (head == null) {
            return false;
        }

        Node current = head;
        while (true) {
            if (current.data == data) {
                return true;
            }
            current = current.next;
            // 指针回到头节点，说明未找到
            if (current == head) {
                break;
            }
        }
        return false;
    }

    /**
     * 更新指定数据的节点
     * @param oldData 旧数据
     * @param newData 新数据
     * @return 更新成功返回true，失败返回false
     */
    public boolean update(double oldData, double newData) {
        if (head == null) {
            return false;
        }

        Node current = head;
        while (true) {
            if (current.data == oldData) {
                current.data = newData;
                return true;
            }
            current = current.next;
            // 指针回到头节点，说明未找到
            if (current == head) {
                break;
            }
        }
        return false;
    }

    /**
     * 获取链表长度
     * @return 链表节点数量
     */
    public int getLength() {
        if (head == null) {
            return 0;
        }

        int count = 1;
        Node current = head.next;
        while (current != head) {
            count++;
            current = current.next;
        }
        return count;
    }

    /**
     * 重写toString()，自定义链表字符串表示
     * @return 链表的字符串形式
     */
    @Override
    public String toString() {
        if (head == null) {
            return "空循环链表";
        }

        List<Double> elements = traverse();
        // 将Double列表转为字符串（处理整数显示，如1.0→1）
        StringBuilder sb = new StringBuilder();
        for (double elem : elements) {
            if (elem == Math.floor(elem)) {  // 判断是否为整数
                sb.append((long) elem);
            } else {
                sb.append(elem);
            }
            sb.append(" -> ");
        }
        sb.append("...");
        return "循环单链表: " + sb.toString();
    }

    // 主方法：测试循环单链表所有功能
    public static void main(String[] args) {
        CircularSinglyLinkedList clist = new CircularSinglyLinkedList();

        // 测试空链表
        System.out.println("链表为空: " + clist.isEmpty());    // true
        System.out.println("链表长度: " + clist.getLength());  // 0
        System.out.println(clist);                            // 空循环链表

        // 添加元素（尾部插入1-5）
        System.out.println("\n添加元素: 1, 2, 3, 4, 5");
        clist.append(1);
        clist.append(2);
        clist.append(3);
        clist.append(4);
        clist.append(5);
        System.out.println(clist);                            // 1 -> 2 -> 3 -> 4 -> 5 -> ...
        System.out.println("链表长度: " + clist.getLength());  // 5

        // 在头部添加元素0
        System.out.println("\n在头部添加元素: 0");
        clist.prepend(0);
        System.out.println(clist);                            // 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> ...

        // 在3后插入3.5
        System.out.println("\n在3后插入: 3.5");
        clist.insertAfter(3, 3.5);
        System.out.println(clist);                            // 0 -> 1 -> 2 -> 3 -> 3.5 -> 4 -> 5 -> ...

        // 查找元素
        System.out.println("\n查找元素:");
        System.out.println("查找3: " + clist.search(3));      // true
        System.out.println("查找10: " + clist.search(10));    // false

        // 更新元素3.5→3.75
        System.out.println("\n更新元素 3.5 -> 3.75");
        clist.update(3.5, 3.75);
        System.out.println(clist);                            // 0 -> 1 -> 2 -> 3 -> 3.75 -> 4 -> 5 -> ...

        // 删除操作
        System.out.println("\n删除头节点");
        clist.deleteHead();
        System.out.println(clist);                            // 1 -> 2 -> 3 -> 3.75 -> 4 -> 5 -> ...

        System.out.println("\n删除尾节点");
        clist.deleteTail();
        System.out.println(clist);                            // 1 -> 2 -> 3 -> 3.75 -> 4 -> ...

        System.out.println("\n删除节点: 3");
        clist.delete(3);
        System.out.println(clist);                            // 1 -> 2 -> 3.75 -> 4 -> ...

        // 清空链表
        System.out.println("\n删除所有节点");
        while (!clist.isEmpty()) {
            clist.deleteHead();
        }
        System.out.println(clist);                            // 空循环链表
    }
}